# 作者: 肖老师
# 2024年11月28日05时59分43秒
# xxxrlmk@163.com
import random
import time


class Sort:
    def __init__(self, count):
        self.length = count  # 排序多少元素
        self.arr = [0] * self.length
        for i in range(self.length):
            self.arr[i] = random.randint(0, 99)
        # self.arr =[13, 80, 41, 4, 89, 46, 74, 61, 75, 37]

    def bubble(self):
        arr = self.arr
        i = self.length - 1
        while i > 0:  # 外层控制无序数的数目
            flag = True  # 如果本身就是有序，提前结束排序
            j = 0
            while j < i:  # 内层控制比较
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
                    flag = False
                j += 1
            if flag:
                break
            i -= 1

    def select(self):
        arr = self.arr
        i = 0
        while i < self.length - 1:
            min_pos = i
            j = i + 1
            while j < self.length:
                if arr[j] < arr[min_pos]:
                    min_pos = j
                j += 1
            arr[i], arr[min_pos] = arr[min_pos], arr[i]
            i += 1

    def insert(self):
        arr = self.arr
        # 外层就是要插入的元素的下标
        i = 1
        while i < self.length:
            insert_val = arr[i]  # 存要插入的元素
            j = i - 1
            while j >= 0:
                if arr[j] > insert_val:
                    arr[j + 1] = arr[j]
                else:
                    break
                j -= 1
            arr[j + 1] = insert_val
            i += 1

    def shell(self):
        arr = self.arr
        # 最外层循环控制步长
        gap = self.length >> 1
        while gap > 0:
            i = gap  # 第一个要插入的数的位置
            while i < self.length:
                insert_val = arr[i]  # 存要插入的元素
                j = i - gap
                while j >= 0:
                    if arr[j] > insert_val:
                        arr[j + gap] = arr[j]
                    else:
                        break
                    j -= gap
                arr[j + gap] = insert_val
                i += 1
            gap >>= 1

    def partition(self, left, right):
        arr = self.arr
        k = left
        # 随机一个位置，在left与right，交换这个位置的元素值与right
        for i in range(left, right):  # i对当前的列表遍历
            if arr[i] < arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k  # 返回分割值下标

    def quick(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick(left, pivot - 1)
            self.quick(pivot + 1, right)

    def ajust_max_heap(self, ajust_pos, length):
        """
        只是调整某一棵子树为大根堆
        :param ajust_pos: 被调整的父亲
        :param length: 列表长度
        :return:
        """
        arr = self.arr
        dad = ajust_pos
        son = 2 * dad + 1
        while son < length:  # 循环什么时候结束
            # 判断是否有右孩子，以及左孩子和右孩子谁大,有逻辑短路，不用担心后半部分语句访问越界
            if son + 1 < length and arr[son] < arr[son + 1]:
                son += 1
            # 拿比较大的孩子和父亲比
            if arr[son] > arr[dad]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap(self):
        arr = self.arr
        for i in range(self.length // 2 - 1, -1, -1):  # 从最后一个父亲结点一致调整到根部
            self.ajust_max_heap(i, self.length)
        # 交换堆顶和列表最后一个元素
        arr[0], arr[self.length - 1] = arr[self.length - 1], arr[0]
        for len in range(self.length - 1, 1, -1):
            self.ajust_max_heap(0, len)  # 不断的把剩余元素调整为大根堆
            arr[0], arr[len - 1] = arr[len - 1], arr[0]  # 交换堆顶与列表的最后一个元素

    def merge(self, low, mid, high):
        arr = self.arr
        arr_copy = arr.copy()
        i = low
        j = mid + 1
        k = low
        while i <= mid and j <= high:
            if arr_copy[i] < arr_copy[j]:
                arr[k] = arr_copy[i]
                k += 1
                i += 1
            else:
                arr[k] = arr_copy[j]
                k += 1
                j += 1
        while i <= mid:
            arr[k] = arr_copy[i]
            k += 1
            i += 1

        while j <= high:
            arr[k] = arr_copy[j]
            k += 1
            j += 1

    def merge_sort(self, low, high):
        if low < high:
            mid = (low + high) // 2
            self.merge_sort(low, mid)  # 排序好前一半
            self.merge_sort(mid + 1, high)  # 排序好后一半
            self.merge(low, mid, high)  # 合并两个有序数组

    def count(self):
        arr = self.arr
        arr_count = [0] * 100
        # 统计arr中每个数出现的次数
        for i in arr:
            arr_count[i] += 1
        # 把数据回填到arr中
        k = 0
        for i in range(100):
            for j in range(arr_count[i]):  # 某个数值出现了多少次
                arr[k] = i
                k += 1

    def use_time(self, sort_method, *args):
        start = time.time()
        sort_method(*args)
        end = time.time()
        print(f'use time{end - start}')


if __name__ == '__main__':
    s = Sort(10)
    print(s.arr)
    # s.bubble()
    # s.select()
    # s.insert()
    # s.shell()
    # s.quick(0,s.length-1)
    # s.heap()
    # s.merge_sort(0, s.length - 1)
    s.count()
    print(s.arr)
    # s.use_time(s.quick,0,s.length-1)
